package com.lin.benchmade.utils;

public class HitPriorityQueue {
	private int size;
	private int maxSize;
	private Hit[] heap;

	public HitPriorityQueue(int size) {
		initialize(size);
	}

	/**
	 * Determines the ordering of objects in this priority queue. Subclasses
	 * must define this one method.
	 * 
	 * @return <code>true</code> iff parameter <tt>a</tt> is less than parameter
	 *         <tt>b</tt>.
	 */
	protected boolean lessThan(Hit a, Hit b) {
		if (a.getBoost() < b.getBoost()) {
			return true;
		} else {
			return false;
		}
	}

	protected Hit getSentinelObject() {
		return null;
	}

	protected final void initialize(int maxSize) {
		size = 0;
		int heapSize;
		if (0 == maxSize)
			// We allocate 1 extra to avoid if statement in top()
			heapSize = 2;
		else {
			if (maxSize == Integer.MAX_VALUE) {
				heapSize = Integer.MAX_VALUE;
			} else {
				heapSize = maxSize + 1;
			}
		}
		heap = new Hit[heapSize]; // Hit is unbounded type, so this
									// unchecked cast works always
		this.maxSize = maxSize;

		Hit sentinel = getSentinelObject();
		if (sentinel != null) {
			heap[1] = sentinel;
			for (int i = 2; i < heap.length; i++) {
				heap[i] = getSentinelObject();
			}
			size = maxSize;
		}
	}

	public final Hit add(Hit element) {
		size++;
		heap[size] = element;
		upHeap();
		return heap[1];
	}

	public Hit insertWithOverflow(Hit element) {
		if (size < maxSize) {
			add(element);
			return null;
		} else if (size > 0 && !lessThan(element, heap[1])) {
			Hit ret = heap[1];
			heap[1] = element;
			updateTop();
			return ret;
		} else {
			return element;
		}
	}

	/** Returns the least element of the PriorityQueue in constant time. */
	public final Hit top() {
		return heap[1];
	}

	/**
	 * Removes and returns the least element of the PriorityQueue in log(size)
	 * time.
	 */
	public final Hit pop() {
		if (size > 0) {
			Hit result = heap[1]; // save first value
			heap[1] = heap[size]; // move last to first
			heap[size] = null; // permit GC of objects
			size--;
			downHeap(); // adjust heap
			return result;
		} else
			return null;
	}

	public final Hit updateTop() {
		downHeap();
		return heap[1];
	}

	/** Returns the number of elements currently stored in the PriorityQueue. */
	public final int size() {
		return size;
	}

	/** Removes all entries from the PriorityQueue. */
	public final void clear() {
		for (int i = 0; i <= size; i++) {
			heap[i] = null;
		}
		size = 0;
	}

	private final void upHeap() {
		int i = size;
		Hit node = heap[i]; // save bottom node
		int j = i >>> 1;
		while (j > 0 && lessThan(node, heap[j])) {
			heap[i] = heap[j]; // shift parents down
			i = j;
			j = j >>> 1;
		}
		heap[i] = node; // install saved node
	}

	private final void downHeap() {
		int i = 1;
		Hit node = heap[i]; // save top node
		int j = i << 1; // find smaller child
		int k = j + 1;
		if (k <= size && lessThan(heap[k], heap[j])) {
			j = k;
		}
		while (j <= size && lessThan(heap[j], node)) {
			heap[i] = heap[j]; // shift up child
			i = j;
			j = i << 1;
			k = j + 1;
			if (k <= size && lessThan(heap[k], heap[j])) {
				j = k;
			}
		}
		heap[i] = node; // install saved node
	}

	protected final Object[] getHeapArray() {
		return (Object[]) heap;
	}
}
